#include <bits/stdc++.h>

using namespace std;

// 不同的子序列
// 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数
// 测试链接 : https://leetcode.cn/problems/distinct-subsequences/

class Solution 
{
public:
	// 已经展示太多次从递归到动态规划了
	// 直接写动态规划吧
    int numDistinct1(string s, string t) 
    {
        const int MOD = 1e9 + 7;
        int m = s.size(), n = t.size();
        // dp[i][j] : s[前缀长度为i]的所有子序列中，有多少个子序列等于t[前缀长度为j]
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 0; i <= m; ++i) dp[i][0] = 1;

        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if(s[i - 1] == t[j - 1])
                {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
                }
            }
        }
        return dp[m][n];
    }

    // 空间压缩
    int numDistinct1(string s, string t) 
    {
        const int MOD = 1e9 + 7;
        int m = s.size(), n = t.size();
        vector<int> dp(n + 1);
        dp[0] = 1;

        for(int i = 1; i <= m; ++i)
        {
            for(int j = n; j >= 1; --j)
            {
                if(s[i - 1] == t[j - 1])
                {
                    dp[j] = (dp[j] + dp[j - 1]) % MOD;
                }
            }
        }
        return dp[n];
    }
};